/*!
 Temelia - Red Black Tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/red_black_tree.h"
#include "include/stack.h"
#include <stdlib.h>

extern stack_t iterating_handlers;
extern stack_t compare_stack;

/*
 * Properties of red black trees :
 * 1. A node is either red or black.
 * 2. The root is black.
 * 3. All external nodes are black, even when the parent is black
 * (The external nodes are the null value children.)
 * 4. Both children of every red node are black.
 * 5. Every simple path from a node to a descendant leaf contains
 * the same number of black nodes, either counting or not counting
 * the null black nodes.
 */

struct _red_black_tree_node_t
{
	/*! user's key */
	void *key;

	unsigned int color;
};

#define GET_RED_BLACK_MEMBER(x, member) (((red_black_tree_node_t)(x))->member)

/*!
 * Encapsulates user's key into a red black node.
 */
static red_black_tree_node_t _red_black_tree_node_new(void *key,
		unsigned int color);

static void _red_black_tree_node_delete(red_black_tree_node_t tree_node);

static void _red_black_tree_internal_handling(void *x, void *context);

static void _red_black_tree_internal_printing_level(void *x, int level,
		void *contextcontext);

static int _red_black_tree_internal_compare(void *x, void *y, void *context);

void _red_black_tree_set_color(red_black_tree_t red_black_tree,
		unsigned int color);

red_black_tree_t red_black_tree_new(void *key)
{
	return _binary_tree_new(_red_black_tree_node_new(key, RED));
}

void red_black_tree_delete_node(red_black_tree_t red_black_tree)
{
	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);

	_red_black_tree_node_delete(_binary_tree_get_key(red_black_tree));
	_delete(red_black_tree);
}

void red_black_tree_delete(red_black_tree_t red_black_tree)
{
	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);

	red_black_tree_delete(_binary_tree_get_left_child(red_black_tree));
	red_black_tree_delete(_binary_tree_get_right_child(red_black_tree));
	red_black_tree_delete_node(red_black_tree);
}

int red_black_tree_compare_trees(red_black_tree_t red_black_tree1,
		red_black_tree_t red_black_tree2, int compare(void *x, void *y,
				void *context), void *context)
{
	return _binary_tree_compare_trees(red_black_tree1, red_black_tree2,
			compare, context);
}

int red_black_tree_is_empty(red_black_tree_t red_black_tree)
{
	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER, -1);

	return (_binary_tree_get_parent(red_black_tree) == NULL)
			&& (_binary_tree_get_left_child(red_black_tree) == NULL)
			&& (_binary_tree_get_right_child(red_black_tree) == NULL)
			&& (GET_RED_BLACK_MEMBER(_binary_tree_get_key(red_black_tree), key)
					== NULL);
}

int red_black_tree_is_leaf(red_black_tree_t red_black_tree)
{
	return _binary_tree_leaf(red_black_tree);
}

int red_black_tree_get_size(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_size(red_black_tree);
}

red_black_tree_t red_black_tree_get_root(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_root(red_black_tree);
}

void *red_black_tree_get_key(red_black_tree_t red_black_tree)
{
	red_black_tree_node_t node;

	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);

	node = _binary_tree_get_key(red_black_tree);

	return node->key;
}

unsigned int red_black_tree_get_color(red_black_tree_t red_black_tree)
{
	red_black_tree_node_t node;

	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER, BLACK);

	node = _binary_tree_get_key(red_black_tree);

	return node->color;
}

red_black_tree_t red_black_tree_get_parent(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_parent(red_black_tree);
}

red_black_tree_t red_black_tree_get_left_child(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_left_child(red_black_tree);
}

red_black_tree_t red_black_tree_get_right_child(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_right_child(red_black_tree);
}

int red_black_tree_get_height(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_height(red_black_tree);
}

int red_black_tree_get_depth(red_black_tree_t red_black_tree)
{
	return _binary_tree_get_depth(red_black_tree);
}

red_black_tree_t red_black_tree_search(red_black_tree_t _red_black_tree,
		void *key, int compare(void *x, void *y, void *context), void *context)
{

	red_black_tree_node_t search_node = _red_black_tree_node_new(key, -1);
	red_black_tree_t aux;

	stack_push(compare_stack, compare);

	aux = _binary_search_tree_search(_red_black_tree, search_node,
			_red_black_tree_internal_compare, context);
	_red_black_tree_node_delete(search_node);

	stack_pop(compare_stack);

	return aux;
}

red_black_tree_t red_black_tree_insert(red_black_tree_t *red_black_tree,
		void *key, int compare(void *x, void *y, void *context), void *context,
		int adjust_root)
{
	red_black_tree_t add = NULL, parent = NULL, aux = NULL, var = NULL, save =
			NULL;
	red_black_tree_node_t add_node = NULL;

	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);

	stack_push(compare_stack, compare);

	add_node = _red_black_tree_node_new(key, RED);

	aux = add = _binary_search_tree_insert(*red_black_tree, add_node,
			_red_black_tree_internal_compare, context);

	// key already exists - no adding in performed
	if (aux == NULL)
	{
		_red_black_tree_node_delete(add_node);
		return NULL;
	}

	while (add != *red_black_tree && red_black_tree_get_color(add) == RED)
	{
		parent = _binary_tree_get_parent(add);

		if (parent == NULL || add == NULL)
			break;

		if (add == _binary_tree_get_left_child(parent))
		{
			var = _binary_tree_get_right_child(parent);

			if (red_black_tree_get_color(var) == RED)
			{
				_red_black_tree_set_color(add, BLACK);
				_red_black_tree_set_color(var, BLACK);
				_red_black_tree_set_color(parent, RED);

				save = parent;
				add = _binary_tree_get_parent(parent);
			}
			else
			{
				if (save == _binary_tree_get_right_child(add))
				{
					_self_balanced_binary_search_tree_rotate_left(add);
					add = save;
				}

				_red_black_tree_set_color(add, BLACK);
				_red_black_tree_set_color(parent, RED);
				_self_balanced_binary_search_tree_rotate_right(parent);
			}
		}
		else
		{
			var = _binary_tree_get_left_child(parent);

			if (red_black_tree_get_color(var) == RED)
			{
				_red_black_tree_set_color(add, BLACK);
				_red_black_tree_set_color(var, BLACK);
				_red_black_tree_set_color(parent, RED);

				save = parent;
				add = _binary_tree_get_parent(parent);
			}
			else
			{
				if (save == _binary_tree_get_left_child(add))
				{
					_self_balanced_binary_search_tree_rotate_right(add);
					add = save;
				}

				_red_black_tree_set_color(add, BLACK);
				_red_black_tree_set_color(parent, RED);
				_self_balanced_binary_search_tree_rotate_left(parent);
			}
		}
	}

	while (adjust_root && _binary_tree_get_parent(*red_black_tree))
		(*red_black_tree) = _binary_tree_get_parent(*red_black_tree);

	stack_pop(compare_stack);

	return aux;
}

int red_black_tree_remove(red_black_tree_t *red_black_tree_, void *key,
		int compare(void *x, void *y, void *context), void *context,
		int adjust_root)
{
	red_black_tree_t replaced = NULL, my_deleted = NULL, brother = NULL;
	red_black_tree_node_t key_encapsulated = NULL;
	int _end = 0;

	if (compare(key, GET_RED_BLACK_MEMBER((*red_black_tree_)->key, key),
			context) == 0 && (*red_black_tree_)->parent == NULL
			&& (*red_black_tree_)->left == NULL && (*red_black_tree_)->right
			== NULL)
	{
		red_black_tree_delete(*red_black_tree_);
		*red_black_tree_ = NULL;
		return 0;
	}

	stack_push(compare_stack, compare);

	// Remove the node as in a binary search tree and then start tree balancing.
	key_encapsulated = _red_black_tree_node_new(key, 0);
	replaced = _binary_search_tree_remove(red_black_tree_, key_encapsulated,
			_red_black_tree_internal_compare, context, &my_deleted);

	_red_black_tree_node_delete(key_encapsulated);
	_ASSERT(my_deleted, ==, NULL, ELEMENT_NOT_FOUND, 0);
	red_black_tree_delete_node(my_deleted);

	/*
	 * If the replaced node is red, then the red-black property is preserved
	 * so no root adjusting is required.
	 */
	if (red_black_tree_get_color(replaced) == BLACK && !_end)
	{
		if (replaced == _binary_tree_get_left_child(_binary_tree_get_parent(
				replaced)))
		{
			brother = _binary_tree_get_right_child(_binary_tree_get_parent(
					replaced));

			if (brother && red_black_tree_get_color(brother) == RED)
			{
				_red_black_tree_set_color(brother, BLACK);
				_red_black_tree_set_color(_binary_tree_get_parent(replaced),
						RED);
				_self_balanced_binary_search_tree_rotate_left(
						_binary_tree_get_parent(replaced));
			}

			if (red_black_tree_get_color(_binary_tree_get_left_child(brother))
					== BLACK && red_black_tree_get_color(
					_binary_tree_get_right_child(brother)) == BLACK)
			{
				_red_black_tree_set_color(brother, RED);
				replaced = _binary_tree_get_parent(replaced);
			}
			else
			{
				if (red_black_tree_get_color(_binary_tree_get_right_child(
						brother)) == BLACK)
				{
					_red_black_tree_set_color(_binary_tree_get_left_child(
							brother), BLACK);
					_red_black_tree_set_color(brother, RED);
					_self_balanced_binary_search_tree_rotate_right(brother);
					brother = _binary_tree_get_right_child(
							_binary_tree_get_parent(replaced));
				}

				_red_black_tree_set_color(brother, red_black_tree_get_color(
						_binary_tree_get_parent(replaced)));
				_red_black_tree_set_color(
						_binary_tree_get_right_child(brother), BLACK);
				_red_black_tree_set_color(_binary_tree_get_parent(replaced),
						BLACK);
				_self_balanced_binary_search_tree_rotate_left(
						_binary_tree_get_parent(replaced));
				_end = 1;
			}
		}
		else
		{
			brother = _binary_tree_get_left_child(_binary_tree_get_parent(
					replaced));

			if (brother && red_black_tree_get_color(brother) == RED)
			{
				_red_black_tree_set_color(brother, BLACK);
				_red_black_tree_set_color(_binary_tree_get_parent(replaced),
						RED);
				_self_balanced_binary_search_tree_rotate_right(
						_binary_tree_get_parent(replaced));
			}

			if (red_black_tree_get_color(_binary_tree_get_right_child(brother))
					== BLACK && red_black_tree_get_color(
					_binary_tree_get_left_child(brother)) == BLACK)
			{
				_red_black_tree_set_color(brother, RED);
				replaced = _binary_tree_get_parent(replaced);
			}
			else
			{
				if (red_black_tree_get_color(_binary_tree_get_left_child(
						brother)) == BLACK)
				{
					_red_black_tree_set_color(_binary_tree_get_right_child(
							brother), BLACK);
					_red_black_tree_set_color(brother, RED);
					_self_balanced_binary_search_tree_rotate_left(brother);
					brother = _binary_tree_get_left_child(
							_binary_tree_get_parent(replaced));
				}

				_red_black_tree_set_color(brother, red_black_tree_get_color(
						_binary_tree_get_parent(replaced)));
				_red_black_tree_set_color(
						_binary_tree_get_right_child(brother), BLACK);
				_red_black_tree_set_color(_binary_tree_get_parent(replaced),
						BLACK);
				_self_balanced_binary_search_tree_rotate_right(
						_binary_tree_get_parent(replaced));
				_end = 1;
			}
		}
	}

	while (adjust_root && _binary_tree_get_parent(*red_black_tree_))
		(*red_black_tree_) = _binary_tree_get_parent(*red_black_tree_);

	stack_pop(compare_stack);

	return 1;
}

red_black_tree_t red_black_tree_get_min(red_black_tree_t red_black_tree)
{
	return _binary_search_tree_get_min(red_black_tree);
}

red_black_tree_t red_black_tree_get_max(red_black_tree_t red_black_tree)
{
	return _binary_search_tree_get_max(red_black_tree);
}

void red_black_tree_preorder(red_black_tree_t red_black_tree, void key_handler(
		void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_preorder(red_black_tree, _red_black_tree_internal_handling,
			context);

	stack_pop(iterating_handlers);
}

void red_black_tree_inorder(red_black_tree_t red_black_tree, void key_handler(
		void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_inorder(red_black_tree, _red_black_tree_internal_handling,
			context);

	stack_pop(iterating_handlers);
}

void red_black_tree_reverse_inorder(red_black_tree_t red_black_tree,
		void key_handler(void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_reverse_inorder(red_black_tree,
			_red_black_tree_internal_handling, context);

	stack_pop(iterating_handlers);
}

void red_black_tree_postorder(red_black_tree_t red_black_tree,
		void key_handler(void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_postorder(red_black_tree, _red_black_tree_internal_handling,
			context);

	stack_pop(iterating_handlers);
}

void red_black_tree_level_order(red_black_tree_t red_black_tree,
		void key_handler(void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_level_order(red_black_tree, _red_black_tree_internal_handling,
			context);

	stack_pop(iterating_handlers);
}

void red_black_tree_show_indented(red_black_tree_t red_black_tree,
		void key_handler(void *x, int level, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);

	_binary_tree_show_indented(red_black_tree,
			_red_black_tree_internal_printing_level, context, 0);

	stack_pop(iterating_handlers);
}

static red_black_tree_node_t _red_black_tree_node_new(void *key,
		unsigned int color)
{
	red_black_tree_node_t red_black_tree;

	red_black_tree = (struct _red_black_tree_node_t *) _new(
			sizeof(struct _red_black_tree_node_t));
	red_black_tree->key = key;
	red_black_tree->color = color;

	return red_black_tree;
}

static void _red_black_tree_node_delete(
		red_black_tree_node_t red_black_tree_node)
{
	_ASSERT(red_black_tree_node, ==, NULL, NULL_POINTER,);

	_delete(red_black_tree_node);
}

static void _red_black_tree_internal_handling(void *x, void *context)
{
	void (*handler)(void *x, void *context);

	handler = stack_top(iterating_handlers);

	_ASSERT(handler, ==, NULL, NULL_POINTER,);

	handler(GET_RED_BLACK_MEMBER(x, key), context);
}

static void _red_black_tree_internal_printing_level(void *x, int level,
		void *context)
{
	void (*user_printing_function_level)(void *, int, void *);

	user_printing_function_level = stack_top(iterating_handlers);

	_ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);

	user_printing_function_level(GET_RED_BLACK_MEMBER(x, key), level, context);
}

static int _red_black_tree_internal_compare(void *x, void *y, void *context)
{
	/*
	 * This is the callback function and can compare red_black_tree_t tree nodes.
	 *
	 * For comparing key from nodes, I save the user comparison function in a global pointer.
	 */
	int (*user_comparison_function)(void *, void *, void *);

	user_comparison_function = stack_top(compare_stack);

	_ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);

	return user_comparison_function(GET_RED_BLACK_MEMBER(x, key),
			GET_RED_BLACK_MEMBER(y, key), context);
}

void _red_black_tree_set_color(red_black_tree_t red_black_tree,
		unsigned int color)
{
	red_black_tree_node_t node;

	_ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);

	node = _binary_tree_get_key(red_black_tree);
	node->color = color;
}
